package com.tianyuan.test2;
import java.util.*;
/**
 * 二叉树的中序遍历
 *
 * @date 2025/10/16 17:04
 * 给定一个二叉树的根节点root，返回它的中序遍历结果。
 * 数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足-1000<val<1000
 * 输入：{1,2,#,#,3} 返回值：[2,3,1]
 * 输入：{} 返回值：[]
 * 输入：{1,2} 返回值：[2,1]
 * 输入：{1,#,2} 返回值：[1,2]
 */

public class Solution {
    /**
     * 二叉树中序遍历（左-根-右）
     * @param root 二叉树的根节点
     * @return 中序遍历结果的整型数组
     */
    public int[] inorderTraversal (TreeNode root) {
        // 创建动态列表存储遍历结果（方便动态添加元素）
        List<Integer> list = new ArrayList();
        // 调用递归遍历方法
        travelsal(root, list);
        // 将列表转换为数组（题目要求返回int[]类型）
        int[] num = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            num[i] = list.get(i);
        }
        return num;
    }
    /**
     * 递归实现中序遍历的辅助方法
     * @param root 当前遍历的节点
     * @param list 用于存储遍历结果的列表
     */
    public void travelsal(TreeNode root, List<Integer> list){
        // 递归终止条件：如果当前节点为空，直接返回
        if(root == null){
            return;
        }
        // 1. 先递归遍历左子树（左）
        if(root.left != null){
            travelsal(root.left, list);
        }
        // 2. 访问当前节点，将值加入结果列表（根）
        list.add(root.val);
        // 3. 再递归遍历右子树（右）
        if(root.right != null){
            travelsal(root.right, list);
        }
    }





    /**
     * 辅助方法：将字符串格式的二叉树表示转换为TreeNode对象
     * 输入格式示例：{1,2,#,#,3} 表示根节点为1，左子树为2，2的左右子树为空，1的右子树为3
     * #表示空节点
     */
    private static TreeNode buildTreeFromString(String input) {
        // 处理空树情况
        if (input == null || input.trim().isEmpty() || input.trim().equals("{}")) {
            return null;
        }
        // 去除首尾的{}，并按逗号分割节点值
        String[] nodes = input.trim().substring(1, input.length() - 1).split(",");
        // 根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0].trim()));
        // 使用队列辅助构建二叉树（层序遍历方式）
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1; // 当前处理的节点索引

        while (!queue.isEmpty() && index < nodes.length) {
            TreeNode current = queue.poll();
            // 处理左子节点
            if (index < nodes.length) {
                String leftVal = nodes[index].trim();
                if (!leftVal.equals("#")) { // 不是空节点
                    current.left = new TreeNode(Integer.parseInt(leftVal));
                    queue.offer(current.left);
                }
                index++;
            }
            // 处理右子节点
            if (index < nodes.length) {
                String rightVal = nodes[index].trim();
                if (!rightVal.equals("#")) { // 不是空节点
                    current.right = new TreeNode(Integer.parseInt(rightVal));
                    queue.offer(current.right);
                }
                index++;
            }
        }
        return root;
    }
    //主方法
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1: 输入{1,2,#,#,3}，预期输出[2,3,1]
        String input1 = "{1,2,#,#,3}";
        TreeNode root1 = buildTreeFromString(input1);
        int[] result1 = solution.inorderTraversal(root1);
        System.out.println("测试用例1: " + Arrays.toString(result1));

        // 测试用例2: 输入{}，预期输出[]
        String input2 = "{}";
        TreeNode root2 = buildTreeFromString(input2);
        int[] result2 = solution.inorderTraversal(root2);
        System.out.println("测试用例2: " + Arrays.toString(result2));

        // 测试用例3: 输入{1,2}，预期输出[2,1]
        String input3 = "{1,2}";
        TreeNode root3 = buildTreeFromString(input3);
        int[] result3 = solution.inorderTraversal(root3);
        System.out.println("测试用例3: " + Arrays.toString(result3));

        // 测试用例4: 输入{1,#,2}，预期输出[1,2]
        String input4 = "{1,#,2}";
        TreeNode root4 = buildTreeFromString(input4);
        int[] result4 = solution.inorderTraversal(root4);
        System.out.println("测试用例4: " + Arrays.toString(result4));
    }
}